class Solution:
    def maxProfit(self, inventory: list, orders: int) -> int:
        inventory.sort()
        same = 1
        right = inventory[-1]
        left = 0
        res = 0
        for i in range(len(inventory)-2, -2, -1):
            if orders == 0:
                break
            if i < 0:
                left = 0
            else:
                left = inventory[i]
            diff = right - left
            if diff == 0:
                same += 1
                continue
            if diff * same <= orders:
                price = (right + left+1) * diff // 2
                res += same * price
                orders -= diff * same
                right = left
                same += 1
            else:
                div, mod = divmod(orders, same)
                left = right - div
                diff = right - left
                price = (right + left+1) * diff // 2
                res += same * price
                res += left * mod
                orders = 0
        return res % (10**9 + 7)
